Scalable Exact Parent Sets Identification in Bayesian Networks Learning with Apache Spark

摘要

In Machine Learning, the parent set identification problem is to find a setof random variables that best explain selected variable given the data and somepredefined scoring function. This problem is a critical component to structurelearning of Bayesian networks and Markov blankets discovery, and thus has manypractical applications, ranging from fraud detection to clinical decisionsupport. In this paper, we introduce a new distributed memory approach to theexact parent sets assignment problem. To achieve scalability, we derivetheoretical bounds to constraint the search space when MDL scoring function isused, and we reorganize the underlying dynamic programming such that thecomputational density is increased and fine-grain synchronization iseliminated. We then design efficient realization of our approach in the ApacheSpark platform. Through experimental results, we demonstrate that the methodmaintains strong scalability on a 500-core standalone Spark cluster, and it canbe used to efficiently process data sets with 70 variables, far beyond thereach of the currently available solutions.